void CreateBTree(BTree &BT,string str)
{
BTree T;int i=0;
    queue<BTree>Q; //??
	if(str[0]!='#'){
		BT=new BTNode;
		BT->data=str[0];
		BT->lchild=BT->rchild=NULL;
		Q.push(BT);
	} 
	else BT=NULL;
	while(!Q.empty())
	{
		T=Q.front();
		Q.pop();
		i++;
		if(str[i]=='#')  T->lchild=NULL;
		else{
			T->lchild=new BTNode;
			T->lchild->data=str[i];
			T->lchild->lchild=T->lchild->rchild=NULL;
			Q.push(T->lchild);
			}
			i++;
		if(str[i]=='#')  T->rchild=NULL;
		else{
			T->rchild=new BTNode;
			T->rchild->data=str[i];
			T->rchild->lchild=T->rchild->rchild=NULL;
			Q.push(T->rchild);
		}
	}
}
void PreOrder( BTree BT )
{
BTree st[50],p;
	int top=-1,n=1;
	if(BT!=NULL){
	top++;
	st[top]=BT;
	while(top>-1){
		BT=st[top];
		top--;
		if(n==1){
		   	cout<<BT->data;
		   	n=2;
		   	}
		else{
		   	cout<<' '<<BT->data;
		   }
		if(BT->rchild!=NULL){
		top++;
		st[top]=BT->rchild;
		}
		if(BT->lchild!=NULL){
		top++;
		st[top]=BT->lchild;
		}
	}
		}
}
void InOrder( BTree BT )
{
	BTree st[50],p;
	int top=-1,n=1;
	if(BT!=NULL){
		while(top>-1||BT!=NULL){
		   while(BT!=NULL){
		   	top++;
		   	st[top]=BT;
		   	BT=BT->lchild;
		   }
			if(top>-1){
			BT=st[top];
			top--;
			if(n==1){
			   	cout<<BT->data;
			   	n=2;
			   }
			   else{
			   	cout<<' '<<BT->data;
			   }
			   BT=BT->rchild;
			}
		}
	} 
}
void PostOrder(BTree bt)
{
	BTree st[50],p;
	int top=-1,n=1,flag;
	if(bt!=NULL){
	do{
		while(bt!=NULL){
		top++;
		st[top]=bt;
		bt=bt->lchild;
	}
	p=NULL;
	flag=-1;
	while(top!=-1&&flag){
	bt=st[top];
	if(bt->rchild==p){
		if(n==1){
	   	cout<<bt->data;
	   	n=2;
	   }
	   else{
	   	cout<<' '<<bt->data;
	   }
	   top--;
	   p=bt;	
	}
		else{
			bt=bt->rchild;
			flag=0;
		}
	}
	}while(top!=-1);
	} 
}
